#include <cstdint>
#include <rbMe.h>

namespace rb_tree
{
    template <typename T>
    rb_node<T>::rb_node()
        : lchild_(nullptr), rchild_(nullptr), parent_(nullptr), color_(RED)
    {
    }
    template <typename T>
    rb_node<T>::~rb_node()
    {
        delete T;
    }
    template <typename T>
    rb_node<T> *rb_node<T>::sibling()
    {
        if (!parent_)
            return nullptr;
        if (this == parent_->lchild_)
            return parent_->rchild_;
        else
            return parent_->lchild_;
    }

    template <typename T>
    inline int rbColor(rb_node<T> *p)
    {
        if (!p)
            return BLACK;
        else
            return p->color_;
    }

    template <typename T>
    rb_tree<T>::rb_tree()
        : root_(nullptr)
    {
    }

    template <typename T>
    rb_tree<T>::~rb_tree()
    {
        del_tree(root_);
        root_ = nullptr;
    }

    template <typename T>
    void rb_tree<T>::rotate_left(rb_node<T> *p)
    {
        rb_node<T> *parent = p->parent_;
        rb_node<T> *rchild = p->rchild_;
        if (!rchild)
            return;

        if (parent)
        {
            if (p == parent->lchild_)
                parent->lchild_ = rchild;
            else
                parent->rchild_ = rchild;
        }
        else
        {
            root_ = rchild;
        }
        rchild->parent_ = parent;

        p->rchild_ = rchild->lchild_;
        if (p->rchild_)
            p->rchild_->parent_ = p;
        rchild->lchild_ = p;
        p->parent_ = rchild;
    }

    template <typename T>
    void rb_tree<T>::rotate_right(rb_node<T> *p)
    {
        rb_node<T> *parent = p->parent_;
        rb_node<T> *lchild = p->lchild_;
        if (!lchild)
            return;

        if (parent)
        {
            if (p == parent->lchild_)
                parent->lchild_ = lchild;
            else
                parent->rchild_ = lchild;
        }
        else
        {
            root_ = lchild;
        }
        lchild->parent_ = parent;

        p->lchild_ = lchild->rchild_;
        if (p->lchild_)
            p->lchild_->parent_ = p;

        lchild->rchild_ = p;
        p->parent_ = lchild;
    }

    template <typename T>
    void rb_tree<T>::del_tree(rb_node<T> *p)
    {
        if (!p)
            return;
        if (p->lchild_)
            del_tree(p->lchild_);
        if (p->rchild_)
            del_tree(p->rchild_);
        delete p;
    }

    template <typename T>
    rb_node<T> *rb_tree<T>::search(rb_node<T> *p, rb_node<T> *&parent)
    {
        rb_node<T> *tmp = root_;
        while (tmp)
        {
            if (0 == cmp_func(tmp, p))
                return tmp;
            else if (0 < cmp_func(tmp, p))
            {
                parent = tmp;
                tmp = tmp->rchild_;
            }
            else if (0 > cmp_func(tmp, p))
            {
                parent = tmp;
                tmp = tmp->lchild_;
            }
        }
    }

    template <typename T>
    void *rb_tree<T>::insert(rb_node<T> *p)
    {
        rb_node<T> *parent = nullptr;
        rb_node<T> *node = search(p, parent);
        if (node)
            return;
        if (0 < cmp_func(parent, p))
            parent->rchild_ = p;
        else if (0 > cmp_func(parent, p))
            parent->lchild_ = p;
        p->parent_ = parent;

        rb_node<T> *p_uncle;
        while ((parent = p->parent_) && RED == rbColor(parent))
        {
            rb_node<T> *grandpa = parent->parent_;
            if (parent == grandpa->lchild_)
            {
                p_uncle = grandpa->rchild_;
                if (RED == rbColor(p_uncle))
                {
                    grandpa->color_ = RED;
                    p_uncle->color_ = BLACK;
                    parent->color_ = BLACK;
                    p = grandpa;
                    continue;
                }

                if (p == parent->rchild_)
                {
                    rotate_left(parent);
                    rb_node *tmp = parent;
                    parent = p;
                    p = tmp;
                }
                parent->color_ = BLACK;
                grandpa->color_ = RED;
                rotate_right(grandpa);
            }
        }

        if (root_)
            root_->color_ = BLACK;
    }
} // namespace rb_tree
